\chapter{Вопрос №1}

Правило суммы. Понятие $k$-сочетания без повторений. Рекуррентное соотношение, треугольник Паскаля, его симметричность. Основные тождества, их формальное и комбинаторное доказательство. Принцип биекции. Биномиальная формула, ее простые следствия.

\section{Правило суммы}

Пусть имеются два неперсекающихся множества $F$ и $S$, тогда:
\begin{equation}
	\left|F\right| + \left|S\right| = \left|F \cup S\right|
\end{equation}
это утверждение называется правилом суммы в комбинаторике, и является одним из основных тождеств (на него опираются комбинаторные доказательства рекуррентных соотношений для сочетаний без и с повторениями, для размещений без повторений, для чисел Белла и многие другие)

\section{Понятие $k$-сочетания без повторений}

Пусть имеется $n$-множество $S$, числом $k$-сочетаний без повторений из $n$ называется количество различных $k$-подмножеств множества $S$, и обозначается как:
\[
	\binom{n}{k}
\]
читается как количество сочетаний без повторений из $n$ по $k$.

\section{Рекуррентное соотношение}

Сопоставим произвольному $n$-множеству множество чисел от $1$ до $n$: $\left\{1, 2, ... n\right\}$. Будем рассматривать все $k$-подмножества такого множества. Разобьем все такие подмножества на два больших непересекающихся класса:
\begin{enumerate}
\item В первый класс попадают только подмножества содержащие элемент $n$. В каждом подмножестве этого класса один элемент известен заранее, а следовательно, чтобы сформировать подмножество нужно выбрать $k-1$ элемент из $n-1$ без повторений, количество способов сделать это $$ \binom{n-1}{k-1} $$.

\item Во сторой класс входят подмножества не содержащие элемента $n$. Чтобы построить такое подмножество нужно выбрать $k$ элементов из $n-1$ элемента без повторений, количество способов сделать это $$ \binom{n-1}{k} $$
\end{enumerate}

так оба класса покрывают все возможные варианты $k$-подмножеств $n$-множества, то рекуррентная формула для числа сочетаний без повторений по правилу суммы выглядит следующим образом:
\begin{align}
	& \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\\
	& \binom{n}{k} = 0, \text{ при } k > n\\
	& \binom{n}{0} = 1, \forall n \ge 0
\end{align}
пользуясь этим соотношением можно построить треугольник (треугольник Паскаля), который окажется симметричным в следующем смысле:
\begin{equation}
	\binom{n}{k} = \binom{n}{n-k}
\end{equation}
комбинаторный смысл заключается в том, что выбирая из $n$-множества $k$ элементов, мы неявно, но однозначно определяем и $n-k$ оставшихся элементов.

\section{Основные тождества}
\subsection{Суммирование по верхнему индексу}
\begin{equation}
\sum_{k=0}^n\binom{k}{m} = \binom{n+1}{m+1}
\end{equation}
\begin{Proof} (Комбинаторное). Разобьем все $\left(m+1\right)$-подмножества $\left(n+1\right)$-множества на $n+1$ класс. В $i$-ый класс $X_i$ содержит подмножества, в которых максимальный элемент $i+1$, при этом $i \in \left\{0,1,...n\right\}$. Мошность $$ \left|X_i\right| = \binom{i}{m} $$
\end{Proof}
\begin{Proof} (Не комбинаторное).
\[
	\begin{split}
		&\binom{k+1}{m+1} = \binom{k}{m} + \binom{k}{m+1} \Rightarrow \binom{k}{m} = \binom{k+1}{m+1} - \binom{k}{m+1} \Rightarrow \\
		&\sum_{k=0}^n\binom{k}{m} = \sum_{k=0}^n\binom{k+1}{m+1} - \sum_{k=0}^n\binom{k}{m+1} \Rightarrow \\
		&\sum_{k=0}^n\binom{k}{m} = \sum_{k=m}^n\binom{k+1}{m+1} - \sum_{k=m+1}^n\binom{k}{m+1} \Rightarrow \\
		&\sum_{k=0}^n\binom{k}{m} = \binom{n+1}{m+1} + \sum_{k=m}^{n-1}\binom{k+1}{m+1} - \sum_{k=m+1}^n\binom{k}{m+1} = \binom{n+1}{m+1}
	\end{split}
\]
\end{Proof}
\subsection{Суммирование по диагонали}
\begin{equation}
\sum_{k=0}^n\binom{m+k}{k} = \binom{m+n+1}{n}
\end{equation}
\begin{Proof} (Комбинаторное). Зафиксируем в множестве $$ \left\{1, 2, ..., n+m+1\right\} $$ элементы $1, 2, ... n$. Разобьем все $n$-подмножества на непересекающиеся классы, так чтобы в $i$-ый класс $X_i$ попали только те подмножества, которые не содержат элемент $i+1$, но содержат все $k < i+1$, где $i \in \left\{0, 1, ... n\right\}$. Тогда:
\[
	\left|X_i\right| = \binom{m+n-i}{n-i} = \binom{m+k}{k}
\]
где $k = n-i \in \left\{0, 1, ... n\right\}$
\end{Proof}
\begin{Proof} (Не комбинаторное).
\[
	\begin{split}
		& \sum_{k=0}^n\binom{m+k}{k} = \sum_{k=0}^n\binom{m+k}{m} = \binom{m + n + 1}{m + 1}
	\end{split}	
\]
по формуле суммирования по верхнему индексу.
\end{Proof}
\subsection{Тождество Вандермонда}
\begin{equation}
\sum_{i=0}^k\binom{m}{i}\binom{n}{k-i} = \binom{n+m}{k}
\end{equation}
\begin{Proof} (Комбинаторное). Разбиваем все $k$-подмножества $\left(m+n\right)$-множества, на блоки $X_i$, где $i$ число элементов из подмножества $\left\{1, 2, ... m\right\}$. Тогда:
\[
	\left|X_i\right| = \binom{m}{i}\binom{n}{k-i}
\]
\end{Proof}
\begin{Proof} (Не комбинаторное). Имеется две опф:
\[
	\begin{split}
		& f_1\left(x\right) = \left(1+x\right)^m \\
		& f_2\left(x\right) = \left(1+x\right)^n
	\end{split}
\]
тогда их произведение с одной стороны:
\[
	f_1\left(x\right)\cdot f_2\left(x\right) = \left(1+x\right)^{m+n} = \sum_{i=0}^{n+m}\binom{n+m}{i}
\]
с другой стороны:
\[
	f_1\left(x\right)\cdot f_2\left(x\right) = \sum_{k=0}^{m+n} \left(\sum_{i=0}^k \binom{m}{i}\binom{n}{k-i}\right) x^k
\]
\end{Proof}
\section{Биномиальная формула}
\begin{equation}
\left(x+y\right)^n = \sum_{i=0}^n\binom{n}{i}x^iy^{n-i}
\end{equation}
Подставим $x = y = 1$:
\begin{equation}
	2^n = \sum_{i=0}^n\binom{n}{i}
\end{equation}
Подставим $x = -y = -1$:
\begin{equation}
	0 = \sum_{i=0}^n\binom{n}{i}\left(-1\right)^i
\end{equation}
Продифференцируем по $x$:
\[
	n\left(x+y\right)^{n-1} = \sum_{i=1}^ni\binom{n}{i}x^{i-1}y^{n-i}
\]
Подставим $x = y = 1$:
\begin{equation}
	n2^{n-1} = \sum_{i=1}^{n}i\binom{n}{i}
\end{equation}
